/**
 * https://leetcode-cn.com/problems/trapping-rain-water/
 * 接雨水 (左边和右边柱子的最大所能支撑的减去当前柱子的高度)
 * @param height 
 */
const trap = (height: number[]): number => {
    const len = height.length;

    // 至少三根柱子才能才能接到水
    if (len <= 2) return 0

    let leftMax = height[0], // 左边的柱子的最大值
        rightMax = height[0], // 右边柱子的最大值
        rightMaxI = 0, // 右边最大柱子的索引
        cap = 0;
    // 第一根和最后一根柱子不用管
    for (let i = 1; i < len - 1; i++) {
        // 更新左边的最大值
        if (height[i] >= leftMax) {
            leftMax = height[i]
        }

        // 如果当前索引大于等于右边最大索引
        if (i >= rightMaxI) {
            // 寻找右边柱子的最大值
            rightMax = height[i + 1]
            rightMaxI = i + 1

            for (let j = i + 2; j < len; j++) {
                // 更新右边的最大值
                if (height[j] > rightMax) {
                    rightMax = height[j]
                    rightMaxI = j;
                }
            }
        }

        // 求当前柱子的所能容纳的水
        const currentTrap = (Math.min(leftMax, rightMax) - height[i])
        // 如果有贡献值, 加到总数中
        cap +=  Math.max(0, currentTrap)

    }

    return cap
};

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
// console.log(trap([4,2,0,3,2,5]))